package demo.DataStrucAndAlgo.Stack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/7/25-07-25-19:53
 * @Description：demo.DataStrucAndAlgo.Stack  逆波兰计算器
 */
public class Reverse_Pu_Calcu {
    public static void main(String[] args) {
        String str = "1+((2+3)*4)-5";    //2*5+8/2-1
        List<String> list = getListString(str);   //拆分字符串
        System.out.println(Arrays.toString(list.toArray()));
        List<String> suffix = parseSuffix(list);   //获取逆波兰表达式
        System.out.println(Arrays.toString(suffix.toArray()));
        System.out.printf("%s=%d",str,calculate(suffix));
    }

    //分割表达式放入list存储表达式
    public static List<String> getListString(String str) {
        List <String> list = new ArrayList<>();
        int index = 0;     //字符串索引标记
        char ch;           //拆分的字符
        String string;     //拼接的字符串
        while(index < str.length()){
            ch = str.charAt(index);
            if(ch<'0' || ch > '9'){    //非数字
                list.add("" + ch);
                index++;
            }else{     //为数字
                string = "";
                //index不越界，且下一位还为数字
                while(index < str.length()&&
                        (ch = str.charAt(index))>='0'&&(ch=str.charAt(index))<='9'){
                    string = string + ch;
                    index++;
                }
                list.add(string);
            }
        }
        return list;
//        String split[] = str.split(" ");
//        for (String temp : split) {
//            list.add(temp);
//        }
 //       return list;
    }

    //中缀表达式转为逆波兰表达式的方法
    public static List<String> parseSuffix(List<String> list){
        DoubleLinkedStack stack1 = new DoubleLinkedStack();    //存储运算符
        List<String> s2 = new ArrayList<>();    //存储数字
        for (String s : list) {
            if(s.matches("\\d+")){    //是数字
                s2.add(s);
            }else{   //（运算符、括号）
                if(s.equals("(")){         // ( 直接入栈
                    stack1.push(s.charAt(0));
                }else if(s.equals(")")){         // ),不断stack1弹出运算符入s2，直到遇到stack1的的(为止，并将这一对括号丢弃
                    while(!(stack1.getTop() == '(')){
                        s2.add(""+stack1.pop());
                    }
                    stack1.pop();    //舍弃括号
                }else if(stack1.isEmpty()){      //s1空，则直接入栈
                    stack1.push(s.charAt(0));
                }else if(stack1.getTop() == '('){       //stack1的栈顶为（，直接入栈
                    stack1.push(s.charAt(0));
                }else if (stack1.prioprity(s.charAt(0)) > stack1.prioprity(stack1.getTop())){   //当前运算符优先级>栈顶优先级，直接入栈
                    stack1.push(s.charAt(0));
                }else{
                    while(!stack1.isEmpty() && stack1.prioprity(s.charAt(0)) <= stack1.prioprity(stack1.getTop())){
                        s2.add("" + stack1.pop());
                    }
                    stack1.push(s.charAt(0));
                }
            }
        }
        //将stack1剩余字符串依次加入s2
        while(!stack1.isEmpty()){
            s2.add(""+stack1.pop());
        }
        return s2;
    }

    //逆波兰表达式计算
    public static int calculate(List<String> list) {
        DoubleLinkedStack stack = new DoubleLinkedStack();
        for(String temp:list){
            if(temp.matches("\\d+")){   //匹配多位数字
                stack.push(Integer.parseInt(temp));
            }else{
                int num1 = stack.pop();
                int num2 = stack.pop();
                int value =  stack.cal(num1,num2,temp.charAt(0));
                stack.push(value);
            }
        }
        return stack.pop();
    }
}
